<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 组合总和 II -->
    <script>
      function dfs(candidates, target) {
        // 对数组进行排序，方便后续去重、剪枝处理
        candidates.sort((a, b) => a - b)
        // 定义输出数组
        let outArray = []
        function recursion(targetValue, combined, index) {
          // 如果targetValue等于零，证明当前组合的和
          // 为target，将当前组合(combined)加入输出数组
          if (targetValue === 0) {
            outArray.push(combined)
            return
          }
          // 如果当前索引超出了给定数组范围，直接return
          if (index >= candidates.length) return
          // 初始化与当前元素不重复的后一个元素的索引为当前元素+1
          let notRepeatingIndex = index + 1
          // 找到与当前元素不重复的后一个元素的索引，由于candidates
          // 为升序，因此仅需要找到与当前元素不同的元素，即可跳过全部
          // 相同的元素
          while (candidates[notRepeatingIndex] == candidates[index]) notRepeatingIndex++
          // 如果当前目标值减去差值小于0，由于candidates为升序
          // 因此后续元素与当前差值依旧会小于0，因此舍去(剪枝)
          // 如果大于等于0则继续递归
          let diff = targetValue - candidates[index]
          if (diff >= 0) {
            // 跳到不重复的元素继续递归
            recursion(targetValue, combined, notRepeatingIndex)
            // 减去当前值，继续递归下一个元素
            recursion(diff, [...combined, candidates[index]], index + 1)
          }
        }
        // 执行递归
        recursion(target, [], 0)
        // 输出结果
        return outArray
      }
      console.log(dfs([10, 1, 2, 7, 6, 1, 5], 8))
    </script>
  </body>
</html>
